package com.lun.swordtowardoffer2.c08;

import java.util.HashMap;
import java.util.Map;

import com.lun.util.BinaryTree.TreeNode;

public class PathSum {

	public int pathSum(TreeNode root, int sum) {
		Map<Integer, Integer> pathSum2Count = new HashMap<>();
		pathSum2Count.put(0, 1);
		return dfs(root, sum, 0, pathSum2Count);
	}
	
	public int dfs(TreeNode node, int sum, int path, Map<Integer, Integer> pathSum2Count) {
		if(node == null) {
			return 0;
		}
		
		path += node.val;
		int count = pathSum2Count.getOrDefault(path - sum, 0);
		
		pathSum2Count.put(path, pathSum2Count.getOrDefault(path, 0) + 1);
		count += dfs(node.left, sum, path, pathSum2Count);
		count += dfs(node.right, sum, path, pathSum2Count);
		pathSum2Count.put(path, pathSum2Count.get(path) - 1);
		
		return count;
	}
	
}
